package com.lb.util;

import java.util.PriorityQueue;

public class LessMoneySplitGold {

    public static int lessMoney(int[] arr) {
        PriorityQueue<Integer> pQ = new PriorityQueue<>(); //1、准备一个小根堆
        for (int i = 0; i < arr.length; i++) { //2、把所有数字扔到小根堆中
            pQ.add(arr[i]);
        }
        int sum = 0;
        int cur = 0;
        while (pQ.size() > 1) {
            cur = pQ.poll() + pQ.poll(); //3、每次弹出两个数字进行结合
            sum += cur;
            pQ.add(cur); //4、把结合的数扔到小根堆中
        }
        return sum;
    }


    public static void main(String[] args) {
        // solution
        int[] arr = {6, 7, 8, 9};
        System.out.println(lessMoney(arr)); //60
    }
}